/**
 * A * 算法
 */
function    AStar (options) {

    this._heuristic = options && options.heuristic  ? options.heuristic : this.defaultHeuristic;
    this._costLogic = options && options.costLogic  ? options.costLogic : this.defaultCostLogic;
    this._diagonals = options && options.diagonals  ? options.diagonals : false;
    this._openHeap  = new BinaryHeap(function (node) {

        return node.Fx;
    });
}

/**
 * 检索
 *
 * @param   Array   matrix  矩阵
 * @param   Object  start   起始位置坐标数据
 * @param   Object  end     目标位置坐标数据
 * @return  Array           路径节点
 */
AStar.prototype.search  = function (matrix, start, end) {

    this._matrix    = matrix;
    this.buildMapByMatrix(matrix);
    this._openHeap.push(this._map[start.y][start.x]);

    while(this._openHeap.size() > 0) {

        var currentNode     = this._openHeap.pop();

        if(this.nodeEqual(currentNode, end)) {

            return  this.getParentPath(currentNode);
        }

        currentNode.closed  = true;
        this.calculateNeighborScore(currentNode, end);
    }

    return          [];
}

/**
 * 建立检索用地图
 *
 * @param   Array   matrix  矩阵
 */
AStar.prototype.buildMapByMatrix    = function (matrix) {

    this._map   = [];

    for (var y = 0;y < matrix.length;y ++) {

        this._map[y]    = [];

        for (var x = 0;x < matrix[y].length;x ++) {

            this._map[y][x] = {
                'x'         : x,
                'y'         : y,
                'Fx'        : 0,
                'Gx'        : 0,
                'Hx'        : 0,
                'isWall'    : matrix[y][x],
                'visited'   : false,
                'closed'    : false,
                'parent'    : null,
                'debug'     : ''
            };
        }
    }
}

/**
 * 比较两个节点是否在同一位置
 *
 * @param   Object  nodeA   节点A
 * @param   Object  nodeB   节点B
 * @return  Boolean         返回比较结果
 */
AStar.prototype.nodeEqual   = function (nodeA, nodeB) {

    return  nodeA.x == nodeB.x && nodeA.y == nodeB.y;
}

/**
 * 从二叉堆中获取结果路径
 *
 * @param   Object  node    当前节点
 * @return  Array           节点路径
 */
AStar.prototype.getParentPath   = function (node) {

    var current = node;
    var result  = [];

    while(current.parent) {
        result.push(current);
        current = current.parent;
    }

    return result.reverse();
}

/**
 * 获取邻居节点列表
 *
 * @param   Object  node    当前节点
 * @return  Array           邻居节点组成的列表
 */
AStar.prototype.getNeighborList = function (node) {

        var result          = [];
        var x               = node.x;
        var y               = node.y;

        var coordinateList  = [
            (x - 1) + ',' + y,
            (x + 1) + ',' + y,
            x + ',' + (y - 1),
            x + ',' + (y + 1)
        ];

        if (this._diagonals) {

            coordinateList = coordinateList.concat([
                (x - 1) + ',' + (y - 1),
                (x + 1) + ',' + (y - 1),
                (x - 1) + ',' + (y + 1),
                (x + 1) + ',' + (y + 1)
            ]);
        }

        for (var offset = 0;offset < coordinateList.length;offset ++) {

            var coordinate  = coordinateList[offset].split(',');
            var deltaX      = coordinate[0];
            var deltaY      = coordinate[1];

            if (this._map[deltaY] && this._map[deltaY][deltaX]) {

                result.push(this._map[deltaY][deltaX]);
            }
        }

        return result;
}

/**
 * 默认启发估算逻辑
 *
 * @param   Object  positionA   位置A
 * @param   Object  positionB   位置B
 * @return  Integer             估算结果
 */
AStar.prototype.defaultHeuristic    = function (positionA, $positionB) {

    var d1  = Math.abs(positionA.x - $positionB.x);
    var d2  = Math.abs(positionA.y - $positionB.y);

    return  d1 + d2;
}

/**
 * 计算邻居节点分数
 *
 * @param   Object  currentNode 当前节点
 * @param   Object  end         结束位置
 */
AStar.prototype.calculateNeighborScore  = function (currentNode, end) {

    var neighborList    = this.getNeighborList(currentNode);

    for (var offset = 0;offset < neighborList.length;offset ++) {

        var neighbor = neighborList[offset];

        if (neighbor.closed || neighbor.isWall) {

            continue;
        }

        var gScore      = currentNode.Gx + this._costLogic(currentNode, neighbor);
        var beenVisited = neighbor.visited;

        if(!beenVisited || gScore < neighbor.Gx) {

            neighbor.visited    = true;
            neighbor.parent     = currentNode;
            neighbor.Hx         = this._heuristic(neighbor, end);
            neighbor.Gx         = gScore;
            neighbor.Fx         = neighbor.Gx + neighbor.Hx;

            if (!beenVisited) {

                this._openHeap.push(neighbor);
            } else {

                this._openHeap.rescoreElement(neighbor);
            }
        }
    }
}

/**
 * 默认扣分逻辑
 *
 * @param   Object  currentNode     当前节点
 * @param   Object  neighborNode    邻居节点
 * @return  Integer                 计算结果
 */
AStar.prototype.defaultCostLogic    = function (currentNode, neighborNode) {

    return  currentNode.x == neighborNode.x || currentNode.y == neighborNode.y
            ? 1
            : Math.sqrt((1 * 1) + (1 * 1));
}
